package com.zwcl.glass.tools.utils;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class CartesianArith {

    public static  <T> List<List<T>> cartesianProduct(T[]... sets) {
        if (sets == null || sets.length == 0) {
            return Collections.emptyList();
        }
        int total = 1;
        //声明进位指针cIndex
        int cIndex = sets.length - 1;
        //声明counterMap(角标 - counter)
        int[] counterMap = new int[sets.length];
        for (int i = 0; i < sets.length; i++) {
            counterMap[i] = 0;
            total *= (sets[i] == null || sets[i].length == 0 ? 1 : sets[i].length);
        }
        List<List<T>> rt = new ArrayList<>(total);
        //开始求笛卡尔积
        while (cIndex >= 0) {
            List<T> element = new ArrayList<>(sets.length);
            for (int j = 0; j < sets.length; j++) {
                T[] set = sets[j];
                //忽略空集
                if (set != null && set.length > 0) {
                    element.add(set[counterMap[j]]);
                }
                //从末位触发指针进位
                if (j == sets.length - 1) {
                    if (set == null || ++counterMap[j] > set.length - 1) {
                        //重置指针
                        counterMap[j] = 0;
                        //进位
                        int cidx = j;
                        while (--cidx >= 0) {
                            //判断如果刚好前一位也要进位继续重置指针进位
                            if (sets[cidx] == null || ++counterMap[cidx] > sets[cidx].length - 1) {
                                counterMap[cidx] = 0;
                                continue;
                            }
                            break;
                        }
                        if (cidx < cIndex) {
                            //移动进位指针
                            cIndex = cidx;
                        }
                    }
                }
            }
            if (element.size() > 0) {
                rt.add(element);
            }
        }
        return rt;
    }

    /**
     * 计算 多个集合的笛卡尔积
     * @param dimValues 存储多个集合的 二维list
     * @return
     */
    public static ArrayList<String> descartes(ArrayList<ArrayList<String>> dimValues) {
        ArrayList<String> result = new ArrayList<String>();

        for (int i = 0 ; i < dimValues.size() ; i++){
            ArrayList<String> curList = dimValues.get(i);

            if(0 == i){//如果是首个集合，直接放输入到结果集中
                for (String tempStr : curList){
                    result.add(tempStr);
                }
                continue;
            }

            selfCopy(result,curList);//将前一个集合的乘积 result，自我复制 curListCount 份，并将当前集合的元素追加到上边
        }
        return result;
    }

    /**
     * 根据当前的集合，将之前的结果集复制
     * @param result　　之前的集合相称的结果集
     * @param curList　　当前集合
     */
    private static void selfCopy(ArrayList<String> result,ArrayList<String> curList) {
        ArrayList<String> tempList = new ArrayList<String>();
        for (String strOfCurList : curList){
            for (String strOfResult : result){
                tempList.add( strOfResult +"|"+ strOfCurList );//因为这里是字符串集合相称，那么其实就是字符串相加。
            }
        }
        result.clear();
        for (String tempStr : tempList){
            result.add(tempStr);
        }
    }

//    @Test
//    public void testCartesianProduct2() {
//        System.out.println(Arrays.deepToString(
//                cartesianProduct(
//                        new String[]{"a", "b"}, new String[]{"0", "1", "2"}, new String[]{"0", "1", "2"}, new String[]{"0", "1", "2"}, new String[]{"0", "1", "2"}, new String[]{"0", "1", "2"}
//                ).toArray()));
//    }

}